package com.leetcode.problems_05;

/**
 *
 * 0019: 删除链表的倒数第n个结点
 *
 *
 * tips：双指针
 *
 *
 * @Author: WuPeng
 * @Date: 2021/5/17 5:39 下午
 */
public class RemoveNthFromEnd {

    public static ListNode solution(ListNode head, int n){
        //虚拟头结点，方便处理删除实际头结点的操作
        ListNode tmpHead = new ListNode(-1);
        tmpHead.next = head;
        ListNode slow = tmpHead, fast = tmpHead;

        //快结点先向后移动 n 步
        while (n-- > 0){
            fast = fast.next;
        }

        //同时移动快慢结点，直到fast指向末尾（fast为null）
        ListNode del_prev = null;
        while (fast != null){
            del_prev = slow;
            fast = fast.next;
            slow = slow.next;
        }

        del_prev.next = slow.next;

        return tmpHead.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        head.next = one;
        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;

        ListNode newHead = solution(head, 3);

        while (newHead != null){
            System.out.println(newHead.val);
            newHead = newHead.next;
        }
    }

}
